package twice.class02;

//逆序对 leetcode:51
//右边多少个数比x小
public class Class03_ReversePair {
    public static int reversePair(int[] arr){
        if(arr == null || arr.length < 2){return 0;}
        return process(arr,0,arr.length-1);
    }
    static int process(int[] arr,int L,int R){
        if(L == R){return 0;}
        int M = L + (R-L) / 2;
        return process(arr,L,M) + process(arr,M + 1,R) + merege(arr,L,M,R);
    }
    static int merege(int[] arr,int L,int M,int R){
        int[] help = new int[R-L+1];
        int p1 = M;
        int p2 = R;
        int i = help.length-1;
        int res = 0;
        while(p1 >= L && p2>=M+1){
            res += arr[p2] < arr[p1] ? (p2 - M) : 0;
            help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
        }
        while (p1 >= L) {
            help[i--] = arr[p1--];
        }
        while (p2 > M) {
            help[i--] = arr[p2--];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }
}
